// 给定一个二叉树，返回其节点值的锯齿形层序遍历
// 锯齿形层序遍历：从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行

// 思路：层序遍历，在每一层的遍历中，记录奇数还是偶数行，如果是奇数行向数组尾部添加，否则向头部添加
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，queue的大小

function zigzagLevelOrder(root) {
    if (!root) {
        return []
    }
    let result = []
    let queue = [root]
    let isOdd = false
    while (queue.length) {
        let len = queue.length
        let level = [] 
        isOdd = !isOdd
        for (let i = 0; i < len; i++) {
            const node = queue.shift() // 取出头部元素
            if (isOdd) {
                level.push(node.val)
            } else {
                level.unshift(node.val)
            }
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        result.push(level)
    }
    return result
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};
console.log(zigzagLevelOrder(root))